package lc_1671_得到山形数组的最少删除次数;

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public int[] getLISArray(int[] nums) {
        int len = nums.length;
        int[] lis = new int[len];
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            int idx = bisect_left(list, nums[i]);
            if (idx == list.size()) {
                list.add(nums[i]);
            } else {
                list.set(idx, nums[i]);
            }
            lis[i] = idx + 1;
        }
        return lis;
    }

    private int bisect_left(List<Integer> list, int num) {
        int l = 0, r = list.size();
        while (l < r) {
            int m = ((r - l) >> 1) + l;
            if (list.get(m) < num) {
                l = m + 1;
            } else {
                r = m;
            }
        }
        return l;
    }

    private int[] reverse(int nums[]) {
        int[] array = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            array[i] = nums[nums.length - i - 1];
        }
        return array;
    }

    public int minimumMountainRemovals(int[] nums) {
        int[] l = getLISArray(nums);
        int[] r = reverse(getLISArray(reverse(nums)));
        int ans = 0;
        for(int i =0;i<nums.length;i++){
            if(l[i] > 1 && r[i] > 1){
                ans = Math.max(ans, l[i] + r[i]);
            }
        }
        return nums.length - ans + 1;
    }
}